/*
如何评价一个算法的好坏？
* 算法的时间复杂度：算法执行的快不快
* 算法的空间复杂度：算法执行费不费内存
* 这两个复杂度用 大O 表达式来表示复杂度
* O(1) 不随着输入规模的变化而变化
* O(n) 随着输入的长度的变化而变化
* 忽略 n 前面的系数 O(2n) / O(3n) .... 统一成 O(n)
* 忽略 n 后面的常数 O(n + 1) / O(n + 2) ... 统一成 O(n)
*/

#include <vector>
#include <iostream>

using namespace std;

// 假设 printVector 是我们要研究的算法
// 时间复杂度：arr 里有多少个元素，打印的语句就执行多少次，
// Big-O 表达式
// 时间复杂度：O(n) n - arr 中元素的个数
// printVector 的执行时间，随着 arr 中元素个数的增大而增大
// 空间复杂度：O(1)
// printVector 占用的内存空间，不随着 arr 的变化而变化
void printVector(const vector<int> &arr) {
  for (int n : arr) {
    cout << n << " ";
  }
}

// 时间复杂度：O(1)
// printVector1 的执行时间，不随着 arr 的变化而变化
// 空间复杂度：O(1)
// printVector1 占用的内存空间，不随着 arr 的变化而变化
void printVector1(const vector<int> &arr) {
  cout << arr.empty() << endl;
}

// 时间复杂度：O(n + m) n,m 表示 arr1 和 arr2 元素的个数
// 表示 printVectors 的执行时间，随着 arr1 和 arr2 元素个数之和的变化而变化。
// 空间复杂度：O(1)
// 表示 printVectors 占用的内存，不随着 arr1 和 arr2 元素个数的变化而变化。
// printVectors 的执行时间，
void printVectors(const vector<int> &arr1, const vector<int> &arr2) {
  for (int n : arr1) {
    cout << n << " "; // 执行 arr1.size() 次
  }
  cout << endl;
  
  for (int n : arr2) {
    cout << n << " "; // 执行 arr2.size() 次
  }
  cout << endl;
}

// 时间复杂度：O(n * m) n,m 表示 arr1 和 arr2 元素的个数
// printVectors1 的执行时间，随着 arr1 和 arr2 元素个数的乘积变化而变化。
// 空间复杂度：O(1)
// 表示 printVectors1 占用的内存，不随着 arr1 和 arr2 元素个数的变化而变化。
void printVectors1(const vector<int> &arr1, const vector<int> &arr2) {
  for (int n : arr1) {
    cout << n << endl; // n 次

    for (int m : arr2) {
      cout << m << " ";
    } // m 次
    cout << endl;
  }
}

// 总结：
// O(1)
// O(n)
// O(m + n)
// O(m * n)

// 空间复杂度：O(n + 1) n 表示 arr 中个元素的个数 => O(n)
// copy 这个算法占用的内存空间，随着 arr 中元素的个数的变化而变化。
// 时间复杂度：O(n) n 表示 arr 中元素的个数
// copy 这个算法的执行时间，随着 arr 中元素个数的变化而变化。
// 
vector<int> copy(const vector<int> &arr) {
  vector<int> result;

  for (int n : arr) {
    result.push_back(n);
  }
  // result 中元素的个数和 arr 是一样的
  // 我们要使用和 arr 一样多的内存空间来保存 result
  return result;
}

// 空间复杂度：O(2n + 1) => O(n)
// copy 这个算法占用的内存空间，随着 arr 中元素的个数的变化而变化。
// 时间复杂度：O(n)
// copy 这个算法的执行时间，随着 arr 中元素个数的变化而变化。
vector<int> copy1(const vector<int> &arr) {
  vector<int> result;

  for (int n : arr) {
    result.push_back(n);
    result.push_back(n);
    result.push_back(n);
  }
  // result 中元素的个数和 arr 是一样的
  // 我们要使用和 arr 一样多的内存空间来保存 result
  return result;
}

